package subjectlist;

/**
 * 题目描述：
 * 数组中有N+2个数，其中，N个数出现了偶数次，两个数出现了奇数次（这两个数不相等），
 * 请用O（1）的空间复杂度，找出这两个数。
 * 注意：不需要知道具体位置，只需要找出这两个数
 */
public class E如何找出数组中出现的奇数次的数 {

    private static class A异或{
        /**
         * 根据异或运算的性质不难发现，任何一个数字异或它自己其结果都等于0。
         * 所以，对于本题中的数组元素而言，如果从头到尾依次异或每一个元素，
         * 那么异或运算的结果自然也就是那个只出现奇数次的数字，
         * 因为出现偶数次的数字会通过异或运算全部消掉。但是通过异或运算，
         * 也仅仅只是消除掉了所有出现偶数次数的数字，
         * 最后异或运算的结果肯定是那两个出现了奇数次的数异或运算的结果。
         * 假设这两个出现奇数次的数分别为a 与b，根据异或运算的性质，
         * 将二者异或运算的结果记为c，由于a与b不相等，所以，c的值自然也不会为0。
         * 此时只需知道c对应的二进制数中某一个位为1的位数N。
         * 例如，十进制数44可以由二进制0010 1100表示，此时可取N=2或者3，或者5，
         * 然后将c与数组中第N位为1的数进行异或，异或结果就是a、b中的一个，然后用c异或其中一个数，
         * 就可以求出另外一个数了。通过上述方法为什么就能得到问题的解呢？其实很简单，
         * 因为c中第N位为1表示a或b中有一个数的第N位也为1，假设该数为a，
         * 那么当将c与数组中第N位为1的数进行异或时，
         * 也就是将x与a外加上其他第N位为1的出现过偶数次的数进行异或，化简即为x与a异或，结果即为b
         */

        public static void get2Num(int []arr){
            if(arr==null || arr.length<1){
                System.out.println("参数不合理");
                return;
            }
            int result=0;
            int position=0;
            for (int i = 0; i < arr.length; i++) {
                result=result^arr[i];
            }

            int tmpResult=result;//临时保存异或结果
            //找出异或结果中其中一个位值为1的数（如1100，位值为位数为2和3）
            for (int i = result; (i&1)==0 ; i=i>>1) {
                position++;
            }
            for (int i = 0; i < arr.length; i++) {
                //异或的结果与所有第position位为1的数异或，结果一定是出现一次的数中其中一个
                if(((arr[i]>>position) & 1)==1){
                    result=result^arr[i];
                }
            }
            System.out.println(result);
            //得到另外一个出现一次的数
            System.out.println(result^tmpResult);
        }

        public static void main(String[] args) {
            int arr[]={3,5,6,6,5,7,2,2};
            get2Num(arr);
        }
    }
}
